//本main函数部分测试内容在注释中
//根据不同需要取用
#include "BinarySearchTree.h"
#include <vector>
#include <time.h>
#include <stdlib.h>
#include <utility>

//打乱数组
template <typename Comparable>
void Shuffle(std::vector<Comparable> &_arr)
{
  srand(time(NULL));
  for(int i=_arr.size()-1;i>0;i--)
    {
      int index = rand()%(i+1);
      std::swap(_arr[index],_arr[i]);
    }
  //  //输出打乱后的数组
  //  for(typename vector<Comparable>::iterator it=_arr.begin();it!=_arr.end();it++)
  //    std::cout<<*it<<'\n';
  //  std::cout<<'\b'<<"Finished Shuffle."<<std::endl;
}

//数组排序
template <typename Comparable>
void BSTSorting(std::vector<Comparable> &_arr, int _mode = 0)
{
  clock_t begin_time = clock();
  if(_mode == 1||_mode == 0)
  {
    BinarySearchTree<Comparable> T;
    if(_mode ==1)
      {
	Shuffle(_arr);
      }
    //将数组输入BST
    for(typename vector<Comparable>::iterator it=_arr.begin();it!=_arr.end();it++)
    {
      T.insert(*it);
    }
    clock_t end_time = clock();
    std::cout<<"Time Cost:"<<(double)(end_time-begin_time)/CLOCKS_PER_SEC<<std::endl;
    //通过BST将数组由小到大顺序输出
    //T.printTree();
    //std::cout<<"Finished Sorting."<<std::endl;
  }
  else
    {
      #ifdef COMMAND
      #warning WRONG INPUT!
      #endif
      return;
    }
};

void double_test(double &N, int _mode)
{
  vector<double> _arr;
  for(double i = 0; i<N; i++)
    _arr.push_back(i);
  BSTSorting(_arr,_mode);
};

int main(int argc, char* argv[])
{
  //测试函数正确性
  double N = 10;
    //测试_mode==0的结果
    std::cout<<"test1:"<<std::endl;
    double_test(N,0);
    //测试_mode==1的结果
    std::cout<<"test2:"<<std::endl;
    double_test(N,1);
    //测试_mode!=0&&_mode!=1的结果
    std::cout<<"test3:"<<std::endl;
    vector<int> arr;
    BSTSorting(arr,2);

  //测试算法效率
  //测试_mode==0时的最坏效率
  std::cin>>N;
  double_test(N,0);
  //测试_mode==1时的平均效率
  const int TIMES = 15;//重复测试次数
  for(int j=0; j<TIMES; j++)
  {
    double_test(N,1);
  }
  return 0;
}
